Harris chain

 ( Markov Processes ) 

In the mathematical study of stochastic processes, a Harris chain is a Markov chain where the chain returns to a particular part of the state space an unbounded number of times.

Harris chains are regenerative processes and are named after Theodore Harris. The theory of Harris chains and Harris recurrence is useful for treating Markov chains on general (possibly uncountably infinite) state spaces.

---

Definition Let $\backslash \{X\_n\backslash \}$ be a Markov chain on a general state space $\backslash Omega$ with stochastic kernel $K$. The kernel represents a generalized one-step transition probability law, so that $P(X\_\{n+1\}\backslash in\; C\backslash mid\; X\_n=x)=K(x,C)$ for all states $x$ in $\backslash Omega$ and all measurable sets $C\backslash subseteq\; \backslash Omega$. The chain $\backslash \{X\_n\backslash \}$ is a Harris chainR. Durrett. Probability: Theory and Examples. Thomson, 2005. . if there exists $A\backslash subseteq\backslash Omega,\backslash varepsilon>0$, and probability measure $\backslash rho$ with $\backslash rho(\backslash Omega)=1$ such that

1. If $\backslash tau\_A:=\backslash inf\; \backslash \{n\backslash geq\; 0:X\_n\backslash in\; A\backslash \}$, then for all $x\backslash in\backslash Omega$.
2. If $x\backslash in\; A$ and $C\backslash subseteq\backslash Omega$ (where $C$ is measurable), then $K(x,\; C)\backslash geq\; \backslash varepsilon\backslash rho(C)$.

The first part of the definition ensures that the chain returns to some state within $A$ with probability 1, regardless of where it starts. It follows that it visits state $A$ infinitely often (with probability 1). The second part implies that once the Markov chain is in state $A$, its next-state can be generated with the help of an independent Bernoulli coin flip. To see this, first note that the parameter $\backslash varepsilon$ must be between 0 and 1 (this can be shown by applying the second part of the definition to the set $C=\backslash Omega$). Now let $x$ be a point in $A$ and suppose $X\_n=x$. To choose the next state $X\_\{n+1\}$, independently flip a biased coin with success probability $\backslash varepsilon$. If the coin flip is successful, choose the next state $X\_\{n+1\}\backslash in\backslash Omega$ according to the probability measure $\backslash rho$. Else (and if ), choose the next state $X\_\{n+1\}$ according to the measure $P(X\_\{n+1\}\backslash in\; C\backslash mid\; X\_n=x)=(K(x,C)-\backslash varepsilon\backslash rho(C))/(1-\backslash varepsilon)$ (defined for all measurable subsets $C\backslash subseteq\; \backslash Omega$).

Two random processes $\backslash \{X\_n\backslash \}$ and $\backslash \{Y\_n\backslash \}$ that have the same probability law and are Harris chains according to the above definition can be coupled as follows: Suppose that $X\_n=x$ and $Y\_n=y$, where $x$ and $y$ are points in $A$. Using the same coin flip to decide the next-state of both processes, it follows that the next states are the same with probability at least $\backslash varepsilon$.

---

Examples

---

Example 1: Countable state space Let Ω be a countable state space. The kernel K is defined by the one-step conditional transition probabilities P X _n+1 for x, y ∈ Ω. The measure ρ is a probability mass function on the states, so that ρ( x) ≥ 0 for all x ∈ Ω, and the sum of the ρ(x) probabilities is equal to one. Suppose the above definition is satisfied for a given set A ⊆ Ω and a given parameter ε > 0. Then P X _n+1 ≥ ερ( c) for all x ∈ A and all c ∈ Ω.

---

Example 2: Chains with continuous densities Let { X _n},  X _n ∈ R ^d be a Markov chain with a Integral kernel that is absolutely continuous with respect to Lebesgue measure:

K( x, dy) = K( x, y)  dy

such that K( x, y) is a continuous function.

Pick ( x₀,  y₀) such that K( x₀,  y₀ ) > 0, and let A and Ω be open sets containing x₀ and y₀ respectively that are sufficiently small so that K( x,  y) ≥ ε > 0 on A ×  Ω. Letting ρ( C) = |Ω ∩  C|/|Ω| where |Ω| is the Lebesgue measure of Ω, we have that (2) in the above definition holds. If (1) holds, then { X _n} is a Harris chain.

---

Reducibility and periodicity In the following $R:=\backslash inf\backslash \{n\backslash ge1:X\_n\backslash in\; A\backslash \}$; i.e. $R$ is the first time after time 0 that the process enters region $A$. Let $\backslash mu$ denote the initial distribution of the Markov chain, i.e. $X\_0\backslash sim\backslash mu$.

Definition: If for all $\backslash mu$, $P\; =1$, then the Harris chain is called recurrent.

Definition: A recurrent Harris chain $X\_n$ is aperiodic if $\backslash exists\; N$, such that $\backslash forall\; n\backslash ge\; N$, $\backslash forall\; \backslash mu,\; PX\_n\backslash in>0$

Theorem: Let $X\_n$ be an aperiodic recurrent Harris chain with stationary distribution $\backslash pi$. If $P\; =1$ then as $n\backslash rightarrow\backslash infty$, $||\backslash mathcal\{L\}(X\_n|X\_0)-\backslash pi||\_\{TV\}\backslash rightarrow\; 0$ where $||\backslash cdot||\_\{TV\}$ denotes the total variation for signed measures defined on the same measurable space.

Post Comment